package com.linkai.pdd2021;

import java.util.Scanner;

/**
 * @Description: 多多的求和计算01
 *               多多路上从左到右有N棵树（编号1～N），其中第i个颗树有和谐值Ai。
 *              多多鸡认为，如果一段连续的树，它们的和谐值之和可以被M整除，那么这个区间整体看起来就是和谐的。
 *              现在多多鸡想请你帮忙计算一下，满足和谐条件的区间的数量。
 *              输入：5 2
 *                    1 2 3 4 5
*               输出：6
 *
 *              思路：for循环遍历所有可能的长度，然后固定连续树的长度，分别用2个指针指向该连续树的头部和尾部，移动指针进行遍历
 *              缺点：题目的测试用例数据过于判断，该算法时间复杂度较高，会运行超时
 * @Author: 林凯
 * @Date: 2021/10/8 22:49
 */
public class Main03 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int A[] = new int[N];
        for(int i = 0;i < N;i++){
            A[i] = sc.nextInt();
        }

        int num  = 0;       // 和谐区间数量
        // 1. 共有 N 颗树，则有 N 种长度连续数，这个 i 就表示一段连续数的长度
        for (int i = 1; i <= N; i++) {
            // 用来遍历一段连续数的头，尾指针
            int left = 0;              // 头指针
            int right = left + i - 1;      // 尾指针

            // 即固定连续树的长度，遍历该长度下所有可能的连续数区间
            while (right <= N - 1) {
                long sum = 0;           // 初始化这段连续树的和谐值
                // 1.1 处理一段连续树的和谐值之和
                for (int j = left; j <= right; j++) {
                    sum += A[j];
                }
                if (sum % M == 0) {
                    num++;      // 和谐区间数量+1
                }

                // 1.2 移动头尾指针
                left++;
                right++;
            }
        }
        System.out.println(num);
    }
}
